#include "avltreewindow.h"
#include <QPainter>
#include <QDialog>
#include <QDialogButtonBox>
#include <QFormLayout>
#include <QTime>
#include <cmath>
#include <algorithm>
#include <cstdlib>

#ifndef M_PI
#define M_PI 3.14159265358979323846
#endif

// AVLTreeVisualizationWidget 实现
AVLTreeVisualizationWidget::AVLTreeVisualizationWidget(QWidget *parent)
    : QWidget(parent), root(nullptr), m_treeWidth(0), m_treeHeight(0),
    m_currentTraverseNode(nullptr), m_currentTraverseIndex(-1),
    m_rotationPivotNode(nullptr), m_currentRotationStep(0)
{
}

AVLTreeVisualizationWidget::~AVLTreeVisualizationWidget()
{
}

void AVLTreeVisualizationWidget::setRoot(AVLNode* rootNode)
{
    root = rootNode;
    calculateTreeDimensions();
    update();
}

int AVLTreeVisualizationWidget::getTreeHeight(AVLNode* node)
{
    if (node == nullptr) return 0;
    return node->height;
}

int AVLTreeVisualizationWidget::getTreeWidth(AVLNode* node)
{
    if (node == nullptr) return 0;
    int maxWidth = 0;
    calculateSubtreeWidth(node, 0, maxWidth);
    return maxWidth;
}

void AVLTreeVisualizationWidget::calculateSubtreeWidth(AVLNode* node, int level, int& maxWidth)
{
    if (node == nullptr) return;

    int currentWidth = (1 << level);
    if (currentWidth > maxWidth) {
        maxWidth = currentWidth;
    }

    calculateSubtreeWidth(node->left, level + 1, maxWidth);
    calculateSubtreeWidth(node->right, level + 1, maxWidth);
}

void AVLTreeVisualizationWidget::calculateTreeDimensions()
{
    if (root == nullptr) {
        m_treeWidth = 1200;
        m_treeHeight = 700;
        return;
    }

    int height = getTreeHeight(root);
    int width = getTreeWidth(root);

    m_treeWidth = width * 300 + 600;
    m_treeHeight = height * 200 + 300;

    if (m_treeWidth < 1200) m_treeWidth = 1200;
    if (m_treeHeight < 700) m_treeHeight = 700;

    setFixedSize(m_treeWidth, m_treeHeight);
    calculateNodePositions();
}

void AVLTreeVisualizationWidget::calculateNodePositions()
{
    if (root == nullptr) return;

    m_nodePositionsX.clear();
    m_nodePositionsY.clear();
    m_nodePointers.clear();

    const int MAX_NODES = 1000;
    AVLNodeQueue q;
    QVector<int> nodeLevels;
    QVector<int> parentIndices;

    q.push(root);
    nodeLevels.push_back(0);
    parentIndices.push_back(-1);

    while (!q.empty() && m_nodePointers.size() < MAX_NODES) {
        AVLNode* current = q.front();
        int level = nodeLevels.first();
        int parentIndex = parentIndices.first();

        q.pop();
        nodeLevels.pop_front();
        parentIndices.pop_front();

        int x, y;

        if (parentIndex == -1) {
            x = m_treeWidth / 2;
            y = 50;
        } else {
            int parentX = m_nodePositionsX[parentIndex];
            int parentY = m_nodePositionsY[parentIndex];
            int horizontalOffset = m_treeWidth / (1 << (level + 1));

            AVLNode* parent = m_nodePointers[parentIndex];
            if (parent->left == current) {
                x = parentX - horizontalOffset;
            } else {
                x = parentX + horizontalOffset;
            }
            y = parentY + 150;
        }

        m_nodePositionsX.push_back(x);
        m_nodePositionsY.push_back(y);
        m_nodePointers.push_back(current);

        int currentIndex = m_nodePointers.size() - 1;

        if (current->left != nullptr) {
            q.push(current->left);
            nodeLevels.push_back(level + 1);
            parentIndices.push_back(currentIndex);
        }

        if (current->right != nullptr) {
            q.push(current->right);
            nodeLevels.push_back(level + 1);
            parentIndices.push_back(currentIndex);
        }
    }
}

QPoint AVLTreeVisualizationWidget::getCurrentTraverseNodePosition() const
{
    for (int i = 0; i < m_nodePointers.size(); i++) {
        if (m_nodePointers[i] == m_currentTraverseNode) {
            return QPoint(m_nodePositionsX[i], m_nodePositionsY[i]);
        }
    }
    return QPoint();
}

int AVLTreeVisualizationWidget::getNodeBalance(AVLNode* node) const
{
    if (node == nullptr) return 0;
    int leftHeight = node->left ? node->left->height : 0;
    int rightHeight = node->right ? node->right->height : 0;
    return leftHeight - rightHeight;
}

void AVLTreeVisualizationWidget::startTraversal(const QVector<AVLNode*>& order)
{
    m_traverseOrder = order;
    m_currentTraverseIndex = 0;
    m_currentTraverseNode = nullptr;
    update();
}

void AVLTreeVisualizationWidget::nextTraversalStep()
{
    if (m_currentTraverseIndex < m_traverseOrder.size()) {
        m_currentTraverseNode = m_traverseOrder[m_currentTraverseIndex];
        m_currentTraverseIndex++;
        update();

        QString result;
        for (int i = 0; i < m_currentTraverseIndex; i++) {
            if (i > 0) result += " ";
            result += QString::number(m_traverseOrder[i]->data);
        }
        emit traversalStepCompleted(result);
    }
}

void AVLTreeVisualizationWidget::resetTraversal()
{
    m_currentTraverseNode = nullptr;
    m_traverseOrder.clear();
    m_currentTraverseIndex = -1;
    update();
}

void AVLTreeVisualizationWidget::startRotationAnimation(AVLNode* pivotNode, const QString& rotationType)
{
    m_rotationPivotNode = pivotNode;
    m_currentRotationType = rotationType;
    m_currentRotationStep = 0;

    // 创建旋转步骤
    m_rotationSteps.clear();
    if (rotationType == "LL") {
        m_rotationSteps << "开始右旋转(LL情况)" << "旋转完成";
    } else if (rotationType == "RR") {
        m_rotationSteps << "开始左旋转(RR情况)" << "旋转完成";
    } else if (rotationType == "LR") {
        m_rotationSteps << "先对左子树左旋" << "再对根节点右旋(LR情况)" << "旋转完成";
    } else if (rotationType == "RL") {
        m_rotationSteps << "先对右子树右旋" << "再对根节点左旋(RL情况)" << "旋转完成";
    }

    update();
}

void AVLTreeVisualizationWidget::nextRotationStep()
{
    if (m_currentRotationStep < m_rotationSteps.size()) {
        emit rotationStepCompleted(m_rotationSteps[m_currentRotationStep]);
        m_currentRotationStep++;
        update();
    }
}

void AVLTreeVisualizationWidget::paintEvent(QPaintEvent* event)
{
    Q_UNUSED(event);

    QPainter painter(this);
    painter.setRenderHint(QPainter::Antialiasing);
    painter.setPen(QPen(Qt::black, 2));

    QFont font = painter.font();
    font.setPointSize(10);
    painter.setFont(font);

    painter.fillRect(rect(), Qt::white);

    if (root == nullptr) {
        painter.drawText(rect(), Qt::AlignCenter, "AVL树为空");
        return;
    }

    drawTree(painter);
}

void AVLTreeVisualizationWidget::drawTree(QPainter& painter)
{
    // 绘制所有连线
    for (int i = 0; i < m_nodePointers.size(); i++) {
        AVLNode* node = m_nodePointers[i];
        int x = m_nodePositionsX[i];
        int y = m_nodePositionsY[i];

        // 左子节点连线
        if (node->left != nullptr) {
            for (int j = 0; j < m_nodePointers.size(); j++) {
                if (m_nodePointers[j] == node->left) {
                    int childX = m_nodePositionsX[j];
                    int childY = m_nodePositionsY[j];

                    int startX = x - 60;
                    int startY = y + 25;
                    int endX = childX;
                    int endY = childY - 25;

                    QColor lineColor = (node == m_rotationPivotNode && m_currentRotationStep > 0) ? Qt::red : Qt::blue;
                    drawPointerLine(painter, startX, startY, endX, endY, lineColor);
                    break;
                }
            }
        } else {
            int startX = x - 60;
            int startY = y + 25;
            drawNullPointer(painter, startX, startY, true);
        }

        // 右子节点连线
        if (node->right != nullptr) {
            for (int j = 0; j < m_nodePointers.size(); j++) {
                if (m_nodePointers[j] == node->right) {
                    int childX = m_nodePositionsX[j];
                    int childY = m_nodePositionsY[j];

                    int startX = x + 60;
                    int startY = y + 25;
                    int endX = childX;
                    int endY = childY - 25;

                    QColor lineColor = (node == m_rotationPivotNode && m_currentRotationStep > 0) ? Qt::red : Qt::blue;
                    drawPointerLine(painter, startX, startY, endX, endY, lineColor);
                    break;
                }
            }
        } else {
            int startX = x + 60;
            int startY = y + 25;
            drawNullPointer(painter, startX, startY, false);
        }
    }

    // 绘制所有节点
    for (int i = 0; i < m_nodePointers.size(); i++) {
        AVLNode* node = m_nodePointers[i];
        int x = m_nodePositionsX[i];
        int y = m_nodePositionsY[i];
        drawAVLNode(painter, node, x, y);
    }
}

void AVLTreeVisualizationWidget::drawAVLNode(QPainter& painter, AVLNode* node, int x, int y)
{
    // 设置节点样式
    painter.setPen(QPen(Qt::black, 2));

    // 高亮当前遍历节点或旋转节点
    if (node == m_currentTraverseNode) {
        painter.setBrush(QBrush(QColor(255, 255, 0))); // 黄色高亮遍历节点
    } else if (node == m_rotationPivotNode && m_currentRotationStep > 0) {
        painter.setBrush(QBrush(QColor(255, 200, 200))); // 红色高亮旋转节点
    } else {
        painter.setBrush(QBrush(Qt::white));
    }

    // 绘制节点外框
    QRect nodeRect(x - 60, y, 120, 50);
    painter.drawRect(nodeRect);

    // 绘制内部垂直线分隔三个区域
    painter.drawLine(x - 20, y, x - 20, y + 50);
    painter.drawLine(x + 20, y, x + 20, y + 50);

    // 绘制三个区域的内容
    QFont font = painter.font();
    font.setPointSize(9);
    painter.setFont(font);

    // 左格子：Lchild
    QRect leftRect(x - 60, y, 40, 50);
    painter.drawText(leftRect, Qt::AlignCenter, "Lchild");

    // 中格子：data和平衡因子
    QRect middleRect(x - 20, y, 40, 50);
    painter.setBrush(QBrush(Qt::lightGray));
    painter.drawRect(middleRect);
    painter.setBrush(QBrush(Qt::white));

    int balance = getNodeBalance(node);
    QString dataText = QString("%1\nb:%2").arg(node->data).arg(balance);
    painter.drawText(middleRect, Qt::AlignCenter, dataText);

    // 右格子：Rchild
    QRect rightRect(x + 20, y, 40, 50);
    painter.drawText(rightRect, Qt::AlignCenter, "Rchild");

    // 绘制指针连接点
    painter.setBrush(QBrush(Qt::blue));
    painter.drawEllipse(x - 60 - 3, y + 25 - 3, 6, 6);
    painter.drawEllipse(x + 60 - 3, y + 25 - 3, 6, 6);

    // 恢复字体大小
    font.setPointSize(10);
    painter.setFont(font);
}

void AVLTreeVisualizationWidget::drawPointerLine(QPainter& painter, int startX, int startY, int endX, int endY, const QColor& color)
{
    painter.setPen(QPen(color, 2));
    painter.drawLine(startX, startY, endX, endY);

    // 计算箭头方向
    double angle = my_atan2(endY - startY, endX - startX);

    // 绘制箭头
    int arrowSize = 8;
    QPointF arrowP1 = QPointF(endX - arrowSize * my_cos(angle + M_PI/6),
                              endY - arrowSize * my_sin(angle + M_PI/6));
    QPointF arrowP2 = QPointF(endX - arrowSize * my_cos(angle - M_PI/6),
                              endY - arrowSize * my_sin(angle - M_PI/6));

    QPolygonF arrowHead;
    arrowHead << QPointF(endX, endY) << arrowP1 << arrowP2;

    painter.setBrush(QBrush(color));
    painter.drawPolygon(arrowHead);
}

void AVLTreeVisualizationWidget::drawNullPointer(QPainter& painter, int startX, int startY, bool isLeft)
{
    painter.setPen(QPen(Qt::red, 2));

    int nullPointerLength = 40;
    int endX, endY;

    if (isLeft) {
        endX = startX - nullPointerLength;
        endY = startY + 20;
    } else {
        endX = startX + nullPointerLength;
        endY = startY + 20;
    }

    painter.drawLine(startX, startY, endX, endY);

    double angle = my_atan2(endY - startY, endX - startX);
    int arrowSize = 8;
    QPointF arrowP1 = QPointF(endX - arrowSize * my_cos(angle + M_PI/6),
                              endY - arrowSize * my_sin(angle + M_PI/6));
    QPointF arrowP2 = QPointF(endX - arrowSize * my_cos(angle - M_PI/6),
                              endY - arrowSize * my_sin(angle - M_PI/6));

    QPolygonF arrowHead;
    arrowHead << QPointF(endX, endY) << arrowP1 << arrowP2;

    painter.setBrush(QBrush(Qt::red));
    painter.drawPolygon(arrowHead);

    painter.setPen(Qt::red);
    QFont font = painter.font();
    font.setPointSize(8);
    painter.setFont(font);

    if (isLeft) {
        painter.drawText(endX - 25, endY + 15, "NULL");
    } else {
        painter.drawText(endX + 5, endY + 15, "NULL");
    }

    painter.setPen(Qt::black);
    font.setPointSize(10);
    painter.setFont(font);
}

// AVLTreeWindow 实现
AVLTreeWindow::AVLTreeWindow(QWidget *parent)
    : QMainWindow(parent), m_root(nullptr), m_size(0), m_isTraversing(false),
    m_isRotating(false), m_traverseSpeed(800)
{
    setupUI();
    updateDisplay();

    // 初始化遍历定时器
    m_traverseTimer = new QTimer(this);
    connect(m_traverseTimer, &QTimer::timeout, this, [this]() {
        if (m_visualizationWidget->isTraversing()) {
            m_visualizationWidget->nextTraversalStep();
        } else {
            m_traverseTimer->stop();
            m_isTraversing = false;
            updateDisplay();
        }
    });

    // 初始化旋转定时器
    m_rotationTimer = new QTimer(this);
    connect(m_rotationTimer, &QTimer::timeout, this, [this]() {
        if (m_visualizationWidget->isRotating()) {
            m_visualizationWidget->nextRotationStep();
        } else {
            m_rotationTimer->stop();
            m_isRotating = false;
            updateDisplay();
        }
    });
}

AVLTreeWindow::~AVLTreeWindow()
{
    clearTree(m_root);
}

// AVL树核心操作
int AVLTreeWindow::getHeight(AVLNode* node)
{
    return node ? node->height : 0;
}

int AVLTreeWindow::getBalance(AVLNode* node)
{
    if (node == nullptr) return 0;
    int leftHeight = getHeight(node->left);
    int rightHeight = getHeight(node->right);
    return leftHeight - rightHeight;
}

AVLNode* AVLTreeWindow::rotateRight(AVLNode* y)
{
    AVLNode* x = y->left;
    AVLNode* T2 = x->right;

    x->right = y;
    y->left = T2;

    y->height = max(getHeight(y->left), getHeight(y->right)) + 1;
    x->height = max(getHeight(x->left), getHeight(x->right)) + 1;

    return x;
}

AVLNode* AVLTreeWindow::rotateLeft(AVLNode* x)
{
    AVLNode* y = x->right;
    AVLNode* T2 = y->left;

    y->left = x;
    x->right = T2;

    x->height = max(getHeight(x->left), getHeight(x->right)) + 1;
    y->height = max(getHeight(y->left), getHeight(y->right)) + 1;

    return y;
}

AVLNode* AVLTreeWindow::insert(AVLNode* node, int value)
{
    if (!node) {
        m_size++;
        return new AVLNode(value);
    }

    if (value < node->data)
        node->left = insert(node->left, value);
    else if (value > node->data)
        node->right = insert(node->right, value);
    else
        return node;

    node->height = 1 + max(getHeight(node->left), getHeight(node->right));

    int balance = getBalance(node);

    // 左左情况
    if (balance > 1 && value < node->left->data) {
        performRotationWithAnimation(node, "LL");
        return rotateRight(node);
    }

    // 右右情况
    if (balance < -1 && value > node->right->data) {
        performRotationWithAnimation(node, "RR");
        return rotateLeft(node);
    }

    // 左右情况
    if (balance > 1 && value > node->left->data) {
        performRotationWithAnimation(node, "LR");
        node->left = rotateLeft(node->left);
        return rotateRight(node);
    }

    // 右左情况
    if (balance < -1 && value < node->right->data) {
        performRotationWithAnimation(node, "RL");
        node->right = rotateRight(node->right);
        return rotateLeft(node);
    }

    return node;
}

AVLNode* AVLTreeWindow::minValueNode(AVLNode* node)
{
    AVLNode* current = node;
    while (current->left != nullptr)
        current = current->left;
    return current;
}

AVLNode* AVLTreeWindow::deleteNode(AVLNode* node, int value)
{
    if (!node) return node;

    if (value < node->data)
        node->left = deleteNode(node->left, value);
    else if (value > node->data)
        node->right = deleteNode(node->right, value);
    else {
        if (!node->left || !node->right) {
            AVLNode* temp = node->left ? node->left : node->right;
            if (!temp) {
                temp = node;
                node = nullptr;
            } else {
                *node = *temp;
            }
            delete temp;
            m_size--;
        } else {
            AVLNode* temp = minValueNode(node->right);
            node->data = temp->data;
            node->right = deleteNode(node->right, temp->data);
        }
    }

    if (!node) return node;

    node->height = 1 + max(getHeight(node->left), getHeight(node->right));
    int balance = getBalance(node);

    // 左左情况
    if (balance > 1 && getBalance(node->left) >= 0) {
        performRotationWithAnimation(node, "LL");
        return rotateRight(node);
    }

    // 左右情况
    if (balance > 1 && getBalance(node->left) < 0) {
        performRotationWithAnimation(node, "LR");
        node->left = rotateLeft(node->left);
        return rotateRight(node);
    }

    // 右右情况
    if (balance < -1 && getBalance(node->right) <= 0) {
        performRotationWithAnimation(node, "RR");
        return rotateLeft(node);
    }

    // 右左情况
    if (balance < -1 && getBalance(node->right) > 0) {
        performRotationWithAnimation(node, "RL");
        node->right = rotateRight(node->right);
        return rotateLeft(node);
    }

    return node;
}

bool AVLTreeWindow::search(AVLNode* node, int value)
{
    if (!node) return false;
    if (value == node->data) return true;
    if (value < node->data) return search(node->left, value);
    return search(node->right, value);
}

void AVLTreeWindow::performRotationWithAnimation(AVLNode* pivotNode, const QString& rotationType)
{
    m_isRotating = true;
    m_visualizationWidget->startRotationAnimation(pivotNode, rotationType);
    m_rotationTimer->start(1000); // 1秒一步
}

void AVLTreeWindow::setupUI()
{
    setWindowTitle("AVL平衡二叉树可视化演示");
    setMinimumSize(1200, 700);
    resize(1200, 700);

    QWidget *centralWidget = new QWidget(this);
    setCentralWidget(centralWidget);

    QHBoxLayout *mainLayout = new QHBoxLayout(centralWidget);

    // 左侧：可视化部分
    QVBoxLayout *leftLayout = new QVBoxLayout();
    QLabel *visualLabel = new QLabel("AVL树可视化:");
    visualLabel->setStyleSheet("font-weight: bold; font-size: 14px;");

    m_scrollArea = new QScrollArea();
    m_scrollArea->setWidgetResizable(true);
    m_scrollArea->setHorizontalScrollBarPolicy(Qt::ScrollBarAsNeeded);
    m_scrollArea->setVerticalScrollBarPolicy(Qt::ScrollBarAsNeeded);
    m_scrollArea->setMinimumSize(900, 650);

    m_visualizationWidget = new AVLTreeVisualizationWidget();
    connect(m_visualizationWidget, &AVLTreeVisualizationWidget::traversalStepCompleted,
            this, &AVLTreeWindow::onTraversalStepCompleted);
    connect(m_visualizationWidget, &AVLTreeVisualizationWidget::rotationStepCompleted,
            this, &AVLTreeWindow::onRotationStepCompleted);
    m_scrollArea->setWidget(m_visualizationWidget);

    leftLayout->addWidget(visualLabel);
    leftLayout->addWidget(m_scrollArea);
    mainLayout->addLayout(leftLayout, 3);

    // 右侧：操作面板
    QVBoxLayout *rightLayout = new QVBoxLayout();
    rightLayout->setSpacing(15);

    QWidget *rightPanel = new QWidget();
    rightPanel->setLayout(rightLayout);
    rightPanel->setMaximumWidth(300);

    // 返回按钮
    QPushButton *returnBtn = new QPushButton("返回主菜单");
    returnBtn->setStyleSheet("QPushButton { background-color: #f0f0f0; border: 1px solid #ccc; padding: 8px; }");
    rightLayout->addWidget(returnBtn);

    // 操作面板
    QGroupBox *opsGroup = new QGroupBox("操作面板");
    opsGroup->setStyleSheet("QGroupBox { font-weight: bold; }");
    QVBoxLayout *opsLayout = new QVBoxLayout(opsGroup);
    opsLayout->setSpacing(10);

    // 插入操作
    QHBoxLayout *insertLayout = new QHBoxLayout();
    m_insertEdit = new QLineEdit();
    m_insertEdit->setPlaceholderText("输入要插入的值");
    QPushButton *insertBtn = new QPushButton("插入");
    insertLayout->addWidget(m_insertEdit);
    insertLayout->addWidget(insertBtn);

    // 删除操作
    QHBoxLayout *deleteLayout = new QHBoxLayout();
    m_deleteEdit = new QLineEdit();
    m_deleteEdit->setPlaceholderText("输入要删除的值");
    QPushButton *deleteBtn = new QPushButton("删除");
    deleteLayout->addWidget(m_deleteEdit);
    deleteLayout->addWidget(deleteBtn);

    // 查找操作
    QHBoxLayout *searchLayout = new QHBoxLayout();
    m_searchEdit = new QLineEdit();
    m_searchEdit->setPlaceholderText("输入要查找的值");
    QPushButton *searchBtn = new QPushButton("查找");
    searchLayout->addWidget(m_searchEdit);
    searchLayout->addWidget(searchBtn);

    // 遍历操作
    QGroupBox *traverseGroup = new QGroupBox("遍历操作");
    QVBoxLayout *traverseLayout = new QVBoxLayout(traverseGroup);
    m_traverseCombo = new QComboBox();
    m_traverseCombo->addItem("前序遍历");
    m_traverseCombo->addItem("中序遍历");
    m_traverseCombo->addItem("后序遍历");
    m_traverseCombo->addItem("层次遍历");

    // 遍历速度控制
    QHBoxLayout *speedLayout = new QHBoxLayout();
    QLabel *speedLabel = new QLabel("速度:");
    QComboBox *speedCombo = new QComboBox();
    speedCombo->addItem("慢速", 1500);
    speedCombo->addItem("中速", 800);
    speedCombo->addItem("快速", 400);
    speedCombo->setCurrentIndex(1);

    connect(speedCombo, QOverload<int>::of(&QComboBox::currentIndexChanged), [this, speedCombo](int index) {
        m_traverseSpeed = speedCombo->itemData(index).toInt();
        if (m_isTraversing) {
            m_traverseTimer->stop();
            m_traverseTimer->start(m_traverseSpeed);
        }
    });

    speedLayout->addWidget(speedLabel);
    speedLayout->addWidget(speedCombo);

    QPushButton *traverseBtn = new QPushButton("执行遍历");
    traverseBtn->setMinimumHeight(35);

    traverseLayout->addWidget(m_traverseCombo);
    traverseLayout->addLayout(speedLayout);
    traverseLayout->addWidget(traverseBtn);

    // 其他操作按钮
    QPushButton *clearBtn = new QPushButton("清空AVL树");
    clearBtn->setMinimumHeight(35);
    QPushButton *randomBtn = new QPushButton("生成随机AVL树");
    randomBtn->setMinimumHeight(35);

    // 将所有按钮添加到操作面板
    opsLayout->addLayout(insertLayout);
    opsLayout->addLayout(deleteLayout);
    opsLayout->addLayout(searchLayout);
    opsLayout->addWidget(traverseGroup);

    QHBoxLayout *otherOpsLayout = new QHBoxLayout();
    otherOpsLayout->addWidget(clearBtn);
    otherOpsLayout->addWidget(randomBtn);
    opsLayout->addLayout(otherOpsLayout);

    // 信息显示部分
    QGroupBox *infoGroup = new QGroupBox("AVL树信息");
    infoGroup->setStyleSheet("QGroupBox { font-weight: bold; }");
    QVBoxLayout *infoLayout = new QVBoxLayout(infoGroup);
    m_display = new QTextEdit();
    m_display->setReadOnly(true);
    m_display->setMaximumHeight(400);
    infoLayout->addWidget(m_display);

    // 将操作面板和信息显示添加到右侧布局
    rightLayout->addWidget(opsGroup);
    rightLayout->addWidget(infoGroup);

    // 添加右侧面板到主布局
    mainLayout->addWidget(rightPanel, 1);

    // 连接信号槽
    connect(insertBtn, &QPushButton::clicked, this, &AVLTreeWindow::onInsert);
    connect(deleteBtn, &QPushButton::clicked, this, &AVLTreeWindow::onDelete);
    connect(searchBtn, &QPushButton::clicked, this, &AVLTreeWindow::onSearch);
    connect(traverseBtn, &QPushButton::clicked, this, &AVLTreeWindow::onTraverse);
    connect(clearBtn, &QPushButton::clicked, this, &AVLTreeWindow::onClear);
    connect(randomBtn, &QPushButton::clicked, this, &AVLTreeWindow::onGenerateRandom);
    connect(returnBtn, &QPushButton::clicked, this, &AVLTreeWindow::onReturnToMainMenu);
}

void AVLTreeWindow::updateDisplay()
{
    QString info = QString("AVL平衡二叉树信息\n\n节点数: %1\n\n").arg(m_size);

    if (m_root == nullptr) {
        info += "AVL树为空";
    } else {
        info += "树的高度: " + QString::number(getHeight(m_root)) + "\n\n";

        // 修复字符串连接问题
        QString balanceStatus;
        if (abs(getBalance(m_root)) <= 1) {
            balanceStatus = "平衡";
        } else {
            balanceStatus = "不平衡";
        }
        info += "平衡状态: " + balanceStatus + "\n\n";

        info += "层次遍历结果: ";
        QVector<AVLNode*> levelOrderNodes;
        levelOrderTraversal(m_root, levelOrderNodes);
        for (AVLNode* node : levelOrderNodes) {
            info += QString::number(node->data) + " ";
        }
        info += "\n\n";

        // 显示各种遍历结果
        info += "前序遍历: ";
        QVector<AVLNode*> preorderNodes;
        preorderTraversal(m_root, preorderNodes);
        for (AVLNode* node : preorderNodes) {
            info += QString::number(node->data) + " ";
        }
        info += "\n\n";

        info += "中序遍历: ";
        QVector<AVLNode*> inorderNodes;
        inorderTraversal(m_root, inorderNodes);
        for (AVLNode* node : inorderNodes) {
            info += QString::number(node->data) + " ";
        }
        info += "\n\n";

        info += "后序遍历: ";
        QVector<AVLNode*> postorderNodes;
        postorderTraversal(m_root, postorderNodes);
        for (AVLNode* node : postorderNodes) {
            info += QString::number(node->data) + " ";
        }

        // 如果正在遍历，显示当前遍历结果
        if (m_isTraversing) {
            info += "\n\n=== 当前遍历过程 ===\n";
            info += m_currentTraverseResult;
        }
    }

    m_display->setText(info);
    m_visualizationWidget->setRoot(m_root);

    // 自动滚动到树的中部
    QSize treeSize = m_visualizationWidget->getTreeSize();
    if (treeSize.width() > m_scrollArea->width()) {
        m_scrollArea->horizontalScrollBar()->setValue(treeSize.width() / 2 - m_scrollArea->width() / 2);
    }
}

// 遍历方法实现
void AVLTreeWindow::preorderTraversal(AVLNode* node, QVector<AVLNode*>& result)
{
    if (node == nullptr) return;
    result.push_back(node);
    preorderTraversal(node->left, result);
    preorderTraversal(node->right, result);
}

void AVLTreeWindow::inorderTraversal(AVLNode* node, QVector<AVLNode*>& result)
{
    if (node == nullptr) return;
    inorderTraversal(node->left, result);
    result.push_back(node);
    inorderTraversal(node->right, result);
}

void AVLTreeWindow::postorderTraversal(AVLNode* node, QVector<AVLNode*>& result)
{
    if (node == nullptr) return;
    postorderTraversal(node->left, result);
    postorderTraversal(node->right, result);
    result.push_back(node);
}

void AVLTreeWindow::levelOrderTraversal(AVLNode* node, QVector<AVLNode*>& result)
{
    if (node == nullptr) return;

    AVLNodeQueue q;
    q.push(node);

    while (!q.empty()) {
        AVLNode* current = q.front();
        q.pop();
        result.push_back(current);

        if (current->left != nullptr) q.push(current->left);
        if (current->right != nullptr) q.push(current->right);
    }
}

void AVLTreeWindow::clearTree(AVLNode* node)
{
    if (node == nullptr) return;
    clearTree(node->left);
    clearTree(node->right);
    delete node;
}

// 槽函数实现
void AVLTreeWindow::onInsert()
{
    QString text = m_insertEdit->text();
    if (text.isEmpty()) {
        QMessageBox::warning(this, "输入错误", "请输入要插入的值");
        return;
    }

    bool ok;
    int value = text.toInt(&ok);
    if (!ok) {
        QMessageBox::warning(this, "输入错误", "请输入有效的整数");
        return;
    }

    m_root = insert(m_root, value);
    m_insertEdit->clear();
    updateDisplay();
    QMessageBox::information(this, "插入成功", QString("节点 %1 已插入").arg(value));
}

void AVLTreeWindow::onDelete()
{
    QString text = m_deleteEdit->text();
    if (text.isEmpty()) {
        QMessageBox::warning(this, "输入错误", "请输入要删除的值");
        return;
    }

    bool ok;
    int value = text.toInt(&ok);
    if (!ok) {
        QMessageBox::warning(this, "输入错误", "请输入有效的整数");
        return;
    }

    if (!search(m_root, value)) {
        QMessageBox::information(this, "查找结果", QString("值 %1 不在树中").arg(value));
        return;
    }

    m_root = deleteNode(m_root, value);
    m_deleteEdit->clear();
    updateDisplay();
    QMessageBox::information(this, "删除成功", QString("节点 %1 已删除").arg(value));
}

void AVLTreeWindow::onSearch()
{
    QString text = m_searchEdit->text();
    if (text.isEmpty()) {
        QMessageBox::warning(this, "输入错误", "请输入要查找的值");
        return;
    }

    bool ok;
    int value = text.toInt(&ok);
    if (!ok) {
        QMessageBox::warning(this, "输入错误", "请输入有效的整数");
        return;
    }

    bool found = search(m_root, value);
    if (found) {
        QMessageBox::information(this, "查找结果", QString("值 %1 在树中").arg(value));
    } else {
        QMessageBox::information(this, "查找结果", QString("值 %1 不在树中").arg(value));
    }
    m_searchEdit->clear();
}

void AVLTreeWindow::onTraverse()
{
    if (m_root == nullptr) {
        QMessageBox::information(this, "遍历结果", "AVL树为空");
        return;
    }

    // 停止之前的遍历
    if (m_isTraversing) {
        m_traverseTimer->stop();
        m_visualizationWidget->resetTraversal();
        m_isTraversing = false;
    }

    QString traverseType = m_traverseCombo->currentText();
    QVector<AVLNode*> traverseOrder;

    if (traverseType == "前序遍历") {
        preorderTraversal(m_root, traverseOrder);
    } else if (traverseType == "中序遍历") {
        inorderTraversal(m_root, traverseOrder);
    } else if (traverseType == "后序遍历") {
        postorderTraversal(m_root, traverseOrder);
    } else if (traverseType == "层次遍历") {
        levelOrderTraversal(m_root, traverseOrder);
    }

    // 开始可视化遍历
    m_isTraversing = true;
    m_currentTraverseResult = "";
    m_visualizationWidget->startTraversal(traverseOrder);
    m_traverseTimer->start(m_traverseSpeed);
}

void AVLTreeWindow::onClear()
{
    QMessageBox::StandardButton reply;
    reply = QMessageBox::question(this, "确认清空", "确定要清空AVL树吗？",
                                  QMessageBox::Yes | QMessageBox::No);
    if (reply == QMessageBox::Yes) {
        // 停止遍历和旋转
        if (m_isTraversing) {
            m_traverseTimer->stop();
            m_visualizationWidget->resetTraversal();
            m_isTraversing = false;
        }
        if (m_isRotating) {
            m_rotationTimer->stop();
            m_isRotating = false;
        }

        clearTree(m_root);
        m_root = nullptr;
        m_size = 0;
        updateDisplay();
        QMessageBox::information(this, "清空成功", "AVL树已清空");
    }
}

void AVLTreeWindow::onGenerateRandom()
{
    QMessageBox::StandardButton reply;
    reply = QMessageBox::question(this, "生成随机AVL树",
                                  "确定要生成随机AVL树吗？这将替换当前AVL树。",
                                  QMessageBox::Yes | QMessageBox::No);
    if (reply == QMessageBox::Yes) {
        // 停止遍历和旋转
        if (m_isTraversing) {
            m_traverseTimer->stop();
            m_visualizationWidget->resetTraversal();
            m_isTraversing = false;
        }
        if (m_isRotating) {
            m_rotationTimer->stop();
            m_isRotating = false;
        }

        clearTree(m_root);
        m_root = nullptr;
        m_size = 0;

        int nodeCount = randomInt(5, 15);
        QSet<int> usedValues;

        for (int i = 0; i < nodeCount; i++) {
            int value;
            do {
                value = randomInt(1, 100);
            } while (usedValues.contains(value));

            usedValues.insert(value);
            m_root = insert(m_root, value);
        }

        updateDisplay();
        QMessageBox::information(this, "生成成功", QString("已生成包含 %1 个节点的随机AVL树").arg(nodeCount));
    }
}

void AVLTreeWindow::onReturnToMainMenu()
{
    emit returnToMainMenu();
    this->close();
}

void AVLTreeWindow::onTraversalStepCompleted(const QString& currentResult)
{
    m_currentTraverseResult = currentResult;
    updateDisplay();

    // 获取当前遍历节点的位置并滚动到该位置
    QPoint nodePos = m_visualizationWidget->getCurrentTraverseNodePosition();
    if (!nodePos.isNull()) {
        scrollToNodePosition(nodePos);
    }
}

void AVLTreeWindow::onRotationStepCompleted(const QString& stepInfo)
{
    updateDisplay();
    // 修复字符串连接问题
    m_display->append("\n旋转步骤: " + stepInfo);
}

void AVLTreeWindow::scrollToNodePosition(const QPoint& nodePos)
{
    if (nodePos.isNull()) return;

    int targetX = nodePos.x() - m_scrollArea->viewport()->width() / 2;
    int targetY = nodePos.y() - m_scrollArea->viewport()->height() / 2;

    targetX = std::max(0, std::min(targetX, m_scrollArea->horizontalScrollBar()->maximum()));
    targetY = std::max(0, std::min(targetY, m_scrollArea->verticalScrollBar()->maximum()));

    m_scrollArea->horizontalScrollBar()->setValue(targetX);
    m_scrollArea->verticalScrollBar()->setValue(targetY);
}

int AVLTreeWindow::randomInt(int min, int max)
{
    static bool seeded = false;
    if (!seeded) {
        srand(QTime::currentTime().msec());
        seeded = true;
    }
    return min + (rand() % (max - min + 1));
}
